package codes.google.leveldb;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicMarkableReference;
import java.util.concurrent.atomic.AtomicReferenceArray;

public class SkipList<K> {
	
	private static class Node<K> {
		K key;
		public Node(K key){
			this.key = key;
		}
		
		
	}
	
	private static class Index<K> {
		AtomicMarkableReference<Node<K>> node;
		AtomicMarkableReference<Index<K>> right;
		AtomicMarkableReference<Index<K>> down;
		public Index(Node<K> node,Index<K> right,Index<K> down){
			this.node = new AtomicMarkableReference<Node<K>>(node,false);
			this.right = new AtomicMarkableReference<Index<K>>(right,false);
			this.down = new AtomicMarkableReference<Index<K>>(down,false);
		}
	}
	
	
	
	
	
	

	private Comparator<? super K> comparator;
	private AtomicMarkableReference<Index<K>> head = null;
	public SkipList(Comparator<? super K> comparator){
		this.comparator = comparator;
		
	}
	
	public SkipList(){
		this.head = new AtomicMarkableReference(new Index<K>(new Node<K>(null),null,null),false);
		
		
	}
	
	public void put(K kkey){
		//find the predecessor by specified key
		Comparable<? super K> key = (Comparable<? super K>) kkey ;
		AtomicMarkableReference<Index<K>> processIndexReference = this.head;
		Index<K> newNode = null;
		int level = 10;
		System.out.println(processIndexReference);
		
		
		for(;;){
			AtomicMarkableReference<Index<K>> rightIndexReference = processIndexReference.getReference().right;
			if (rightIndexReference.getReference()!=null){
				processIndexReference = this.insertNode(processIndexReference, newNode);
				// add the new Index to this;
			}
			// if the rightNode == null ,that represent the processNode is the last one of this level. then should look down.
			AtomicMarkableReference<Index<K>> downIndexReference = processIndexReference.getReference().down;
			if (downIndexReference.getReference() != null){
				processIndexReference = downIndexReference;
				
			}
			//if the down is null,represent processIndexReference is the last level of skip list
			processIndexReference = this.insertNode(processIndexReference, newNode);
		}
		
//		while(level>0){
//			if(rightIndexReference.getReference()==null){
//				level--;
//				continue;
//			}
//			for (;;){
//				rightIndexReference = this.searchNode(rightIndexReference,key);
//				Index<K> rightIndex = rightIndexReference.getReference();
//				if(rightIndexReference.compareAndSet(rightIndex, newNode, false, false)){
//					break;
//				}
//			}
//			level--;
//		}
		
	}	
	
	
	private AtomicMarkableReference<Index<K>> insertNode(AtomicMarkableReference<Index<K>> startNodeReference,Index<K> newNode){
		Comparable<? super K> key = (Comparable<? super K>) newNode.node.getReference().key;
		
		AtomicMarkableReference<Index<K>> currentNodeReference = startNodeReference;
		AtomicMarkableReference<Index<K>> predecessorNodeReference = currentNodeReference;
		for(;;){
			if(!(key.compareTo(currentNodeReference.getReference().node.getReference().key)<0)){
				predecessorNodeReference = currentNodeReference;
				currentNodeReference = currentNodeReference.getReference().right;
				continue;
			}
			if(predecessorNodeReference.getReference().right.compareAndSet(currentNodeReference.getReference(), newNode, false, false)){
				break;
			}
			
		}
//		while(!(key.compareTo(currentNodeReference.getReference().node.getReference().key)<0)){
//			
//		}
		return new AtomicMarkableReference(newNode,false);
	}
	

	
	public void delete(K key){
		
	}
	
	public static void main(String arg[]){
		SkipList<String> list = new SkipList<String>();
		list.put("1");
		list.put("1");
		list.put("1");
		list.put("1");
		list.put("1");
		
	}
}
